home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc™ Source Code / Utilities / LinkList.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-28  |  15.0 KB  |  623 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        LinkList.cpp
  3.  
  4.     Contains:    Linked-list class w/iterator
  5.  
  6.     Owned by:    Reggie Adkins
  7.  
  8.     Copyright:    © 1993-96 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.  
  12.          <3>     5/24/96    jpa        Fixed header comment.
  13.          <2>     5/24/96    jpa        1339104: Inlined methods for efficiency
  14.                                     (EditorSetup)
  15.  
  16.     To Do:
  17. */
  18.  
  19. #ifndef _LINKLIST_
  20. #include "LinkList.h"
  21. #endif
  22.  
  23. #ifndef _EXCEPT_
  24. #include "Except.h"
  25. #endif
  26.  
  27. #ifndef __ERRORS__
  28. #include <Errors.h>
  29. #endif
  30.  
  31. #ifndef _ODDEBUG_
  32. #include "ODDebug.h"
  33. #endif
  34.  
  35. #ifndef _UTILERRS_
  36. #include "UtilErrs.h"
  37. #endif
  38.  
  39. #pragma segment ODLinkedList
  40.  
  41. //==============================================================================
  42. // Constants
  43. //==============================================================================
  44.  
  45. //==============================================================================
  46. // Scalar Types
  47. //==============================================================================
  48.  
  49. //==============================================================================
  50. // Local Classes
  51. //==============================================================================
  52.  
  53. //==============================================================================
  54. // Global Variables
  55. //==============================================================================
  56.  
  57. //==============================================================================
  58. // Function Prototype
  59. //==============================================================================
  60.  
  61.  
  62. //==============================================================================
  63. // Link
  64. //==============================================================================
  65.  
  66.  
  67.  
  68. // Many of the simple link methods are inlines; see List.h for implementations.
  69.  
  70.  
  71. //------------------------------------------------------------------------------
  72. // Link::Link
  73. //
  74. // Constructor for Link
  75. //------------------------------------------------------------------------------
  76.  
  77. Link::Link()                            
  78. { 
  79.     fNext = kODNULL; 
  80.     fPrevious = kODNULL;
  81. }
  82.  
  83. //------------------------------------------------------------------------------
  84. // Link::Link
  85. //
  86. // Constructor for Link
  87. //------------------------------------------------------------------------------
  88.  
  89. Link::Link(Link* next, Link* previous)                            
  90. { 
  91.     fNext = next; 
  92.     fPrevious = previous;
  93. }
  94.  
  95. //------------------------------------------------------------------------------
  96. // Link::Link
  97. //
  98. // Copy constructor for Link
  99. //------------------------------------------------------------------------------
  100.  
  101. Link::Link( const Link &link )                            
  102. { 
  103.     fNext = link.fNext; 
  104.     fPrevious = link.fPrevious;
  105. }
  106.  
  107. //------------------------------------------------------------------------------
  108. // Link::Link
  109. //
  110. // Destructor for Link
  111. //------------------------------------------------------------------------------
  112.  
  113. Link::~Link()                                            
  114. {
  115. }
  116.  
  117. //------------------------------------------------------------------------------
  118. // Link::Remove
  119. //
  120. // Remove a link from its list (if any). DO NOT call this directly if there are
  121. // any iterators active on the list; use LinkedList::Remove instead.
  122. //------------------------------------------------------------------------------
  123.  
  124. void    Link::Remove( )
  125. {
  126.     if( fPrevious )
  127.         fPrevious->SetNext(fNext);
  128.     if( fNext )
  129.         fNext->SetPrevious(fPrevious);
  130.     fNext = kODNULL;
  131.     fPrevious = kODNULL;
  132. }
  133.  
  134. //------------------------------------------------------------------------------
  135. // Link::AddBefore
  136. //
  137. // Add a link to a list before another link. It must not already be on any list.
  138. // DO NOT call this directly if there are any iterators active on the list;
  139. // use LinkedList::Remove instead.
  140. //------------------------------------------------------------------------------
  141.  
  142. void    Link::AddBefore( Link *link )
  143. {
  144.     ASSERT(link!=kODNULL,paramErr);
  145.     WASSERT(fNext==kODNULL);
  146.     WASSERT(fPrevious==kODNULL);
  147.     fNext = link;
  148.     fPrevious = link->GetPrevious();
  149.     fPrevious->SetNext(this);
  150.     fNext->SetPrevious(this);
  151. }
  152.  
  153. //------------------------------------------------------------------------------
  154. // Link::AddAfter
  155. //
  156. // Add a link to a list after another link. It must not already be on any list.
  157. // DO NOT call this directly if there are any iterators active on the list;
  158. // use LinkedList::Remove instead.
  159. //------------------------------------------------------------------------------
  160.  
  161. void    Link::AddAfter( Link *link )
  162. {
  163.     ASSERT(link!=kODNULL,paramErr);
  164.     WASSERT(fNext==kODNULL);
  165.     WASSERT(fPrevious==kODNULL);
  166.     fPrevious = link;
  167.     fNext = link->GetNext();
  168.     fPrevious->SetNext(this);
  169.     fNext->SetPrevious(this);
  170. }
  171.  
  172. //======================================================================================
  173. // Class LinkedList
  174. //======================================================================================
  175.  
  176. //------------------------------------------------------------------------------
  177. // LinkedList::LinkedList
  178. //
  179. // Constructor for LinkedList
  180. //------------------------------------------------------------------------------
  181.  
  182. LinkedList::LinkedList()
  183.     :fSentinel(&fSentinel,&fSentinel),
  184.      fSeed(0)
  185. {
  186. }
  187.  
  188. //------------------------------------------------------------------------------
  189. // LinkedList::IsEmpty
  190. //
  191. // Description
  192. //------------------------------------------------------------------------------
  193.  
  194. ODBoolean LinkedList::IsEmpty() const
  195. {
  196.     return this->IsSentinel( fSentinel.GetNext() );
  197. }
  198.  
  199. //------------------------------------------------------------------------------
  200. // LinkedList::Count
  201. //
  202. // Description
  203. //------------------------------------------------------------------------------
  204.  
  205. ODULong LinkedList::Count() const
  206. {
  207.     Link* l = fSentinel.GetNext();
  208.     ODULong count = 0;
  209.     while (this->NotSentinel(l))
  210.     {
  211.         count++;
  212.         l = l->GetNext();
  213.         ASSERT(l!=kODNULL,kODErrAssertionFailed);
  214.     }
  215.     return count;
  216. }
  217.  
  218. //------------------------------------------------------------------------------
  219. // LinkedList::Includes
  220. //
  221. // Does the list include a particular link?
  222. //------------------------------------------------------------------------------
  223.  
  224. ODBoolean LinkedList::Includes( const Link *link ) const
  225. {
  226.     Link* l = fSentinel.GetNext();
  227.     while (this->NotSentinel(l))
  228.     {
  229.         if( l == link )
  230.             return kODTrue;
  231.         else
  232.             l = l->GetNext();
  233.     }
  234.     return kODFalse;
  235. }
  236.  
  237. //------------------------------------------------------------------------------
  238. // LinkedList::DeleteAllLinks
  239. //
  240. // Description
  241. //------------------------------------------------------------------------------
  242.  
  243. void    LinkedList::DeleteAllLinks()
  244. {
  245.  
  246.     Link* l = fSentinel.GetNext();
  247.     Link* n = l;
  248.     while (this->NotSentinel(n))
  249.     {
  250.         n = l->GetNext();
  251.         delete l;    
  252.         l = n;
  253.     }
  254.     fSentinel.SetNext(&fSentinel);
  255.     fSentinel.SetPrevious(&fSentinel);
  256.     fSeed++;
  257. }
  258.  
  259. //------------------------------------------------------------------------------
  260. // LinkedList::RemoveAll
  261. //
  262. // Description
  263. //------------------------------------------------------------------------------
  264.  
  265. void    LinkedList::RemoveAll()
  266. {
  267.  
  268.     Link* l = fSentinel.GetNext();
  269.     Link* n = l;
  270.     while (this->NotSentinel(l))
  271.     {
  272.         n = l->GetNext();
  273.         l->SetNext(kODNULL);
  274.         l->SetPrevious(kODNULL);
  275.         l = n;
  276.     }
  277.     fSentinel.SetNext(&fSentinel);
  278.     fSentinel.SetPrevious(&fSentinel);
  279. }
  280.  
  281. //------------------------------------------------------------------------------
  282. // LinkedList::Remove
  283. //
  284. // Description
  285. //------------------------------------------------------------------------------
  286.  
  287. void    LinkedList::Remove(Link& aLink)
  288. {
  289.     fSeed++;
  290.     aLink.Remove();
  291. }
  292.  
  293. //------------------------------------------------------------------------------
  294. // LinkedList::RemoveFirst
  295. //
  296. // Description
  297. //------------------------------------------------------------------------------
  298.  
  299. Link* LinkedList::RemoveFirst()
  300. {
  301.     Link* old = fSentinel.GetNext();
  302.     if (this->NotSentinel(old))
  303.     {
  304.         fSeed++;
  305.         old->Remove();
  306.         return old;
  307.     }
  308.     else
  309.     {
  310.         return kODNULL;
  311.     }
  312. }
  313.  
  314. //------------------------------------------------------------------------------
  315. // LinkedList::RemoveLast
  316. //
  317. // Description
  318. //------------------------------------------------------------------------------
  319.  
  320. Link* LinkedList::RemoveLast()
  321. {
  322.     Link* old = fSentinel.GetPrevious();
  323.     if (this->NotSentinel(old))
  324.     {
  325.         fSeed++;
  326.         old->Remove();
  327.         return old;
  328.     }
  329.     else
  330.     {
  331.         return kODNULL;
  332.     }
  333. }
  334.  
  335. //------------------------------------------------------------------------------
  336. // LinkedList::AddFirst
  337. //
  338. // Description
  339. //------------------------------------------------------------------------------
  340.  
  341. void    LinkedList::AddFirst(Link* link)
  342. {
  343.     link->AddAfter(this->GetSentinel());
  344.     fSeed++;
  345. }
  346.  
  347. //------------------------------------------------------------------------------
  348. // LinkedList::AddLast( Link )
  349. //
  350. // Description
  351. //------------------------------------------------------------------------------
  352.  
  353. void    LinkedList::AddLast(Link* link)
  354. {
  355.     link->AddBefore(this->GetSentinel());
  356.     fSeed++;
  357. }
  358.  
  359. //------------------------------------------------------------------------------
  360. // LinkedList::AddLast( LinkedList )
  361. //
  362. // Append contents of another list to my end. (Other list becomes empty.)
  363. //------------------------------------------------------------------------------
  364.  
  365. void    LinkedList::AddLast( LinkedList &list )
  366. {
  367.     if( !list.IsEmpty() ) {
  368.         Link *myLast = fSentinel.GetPrevious();
  369.         Link *itsFirst = list.First();
  370.         myLast->SetNext(itsFirst);
  371.         itsFirst->SetPrevious(myLast);
  372.         
  373.         Link *itsLast = list.Last();
  374.         itsLast->SetNext(this->GetSentinel());
  375.         fSentinel.SetPrevious(itsLast);
  376.         
  377.         list.fSentinel.SetNext(this->GetSentinel());
  378.         list.fSentinel.SetPrevious(this->GetSentinel());
  379.  
  380.         fSeed++;
  381.         list.fSeed++;
  382.     }
  383. }
  384.  
  385. //------------------------------------------------------------------------------
  386. // LinkedList::AddLastUnique( LinkedList )
  387. //
  388. // Append contents of another list (w/o duplication) to my end.
  389. //------------------------------------------------------------------------------
  390.  
  391. void    LinkedList::AddLastUnique( LinkedList &list )
  392. {
  393.     for( Link *link = fSentinel.GetNext(); this->NotSentinel(link); link=link->GetNext() )
  394.         if( list.Includes(link) )
  395.             list.Remove(*link);
  396.     this->AddLast(list);
  397. }
  398.  
  399. //------------------------------------------------------------------------------
  400. // LinkedList::AddBefore
  401. //
  402. // Description
  403. //------------------------------------------------------------------------------
  404.  
  405. void LinkedList::AddBefore(Link& existing, Link* link)
  406. {
  407.     link->AddBefore(&existing);
  408.     fSeed++;
  409. }
  410.  
  411. //------------------------------------------------------------------------------
  412. // LinkedList::AddAfter
  413. //
  414. // Description
  415. //------------------------------------------------------------------------------
  416.  
  417. void LinkedList::AddAfter(Link& existing, Link* link)
  418. {
  419.     link->AddAfter(&existing);
  420.     fSeed++;
  421. }
  422.  
  423. //------------------------------------------------------------------------------
  424. // LinkedList::After
  425. //
  426. // Description
  427. //------------------------------------------------------------------------------
  428.  
  429. Link* LinkedList::After(const Link& link) const
  430. {
  431.     Link *next = link.GetNext();
  432.     if( this->IsSentinel(next) )
  433.         return kODNULL;
  434.     else
  435.         return next;
  436. }
  437.  
  438. //------------------------------------------------------------------------------
  439. // LinkedList::Before
  440. //
  441. // Description
  442. //------------------------------------------------------------------------------
  443.  
  444. Link* LinkedList::Before(const Link& link) const
  445. {
  446.     Link *prev = link.GetPrevious();
  447.     if( this->IsSentinel(prev) )
  448.         return kODNULL;
  449.     else
  450.         return prev;
  451. }
  452.  
  453. //------------------------------------------------------------------------------
  454. // LinkedList::First
  455. //
  456. // Description
  457. //------------------------------------------------------------------------------
  458.  
  459. Link*    LinkedList::First()  const
  460. {
  461.     return this->NotSentinel(fSentinel.GetNext()) ? fSentinel.GetNext() : (Link*) kODNULL;
  462. }
  463.  
  464. //------------------------------------------------------------------------------
  465. // LinkedList::Last
  466. //
  467. // Description
  468. //------------------------------------------------------------------------------
  469.  
  470. Link* LinkedList::Last() const
  471. {
  472.     return this->NotSentinel(fSentinel.GetPrevious()) ? fSentinel.GetPrevious() : (Link*) kODNULL;
  473. }
  474.  
  475.  
  476. //======================================================================================
  477. // Class LinkedListIterator
  478. //======================================================================================
  479.  
  480. //------------------------------------------------------------------------------
  481. // LinkedListIterator::LinkedListIterator
  482. //
  483. // Constructor for LinkedListIterator
  484. //------------------------------------------------------------------------------
  485.  
  486. LinkedListIterator::LinkedListIterator(LinkedList* list)
  487. {
  488.     fList = list;
  489.     fCurrent = kODNULL;
  490.     fNext = kODNULL;
  491.     fPrevious = kODNULL;
  492.     fSentinel = &list->fSentinel;
  493.     fSeed = fList->fSeed;    
  494. }
  495.  
  496. //------------------------------------------------------------------------------
  497. // LinkedListIterator::First
  498. //
  499. // Description
  500. //------------------------------------------------------------------------------
  501.  
  502. Link* LinkedListIterator::First()
  503. {
  504.     if (fList == kODNULL)
  505.         return kODNULL;
  506.         
  507.     if (fSeed != fList->fSeed)
  508.         THROW(kODErrIteratorOutOfSync);
  509.         
  510.     fCurrent = fList->First();
  511.     return fCurrent;
  512. }
  513.  
  514. //------------------------------------------------------------------------------
  515. // LinkedListIterator::Next
  516. //
  517. // Description
  518. //------------------------------------------------------------------------------
  519.  
  520. Link* LinkedListIterator::Next()
  521. {
  522.     if (fSeed != fList->fSeed)
  523.         THROW(kODErrIteratorOutOfSync);
  524.  
  525.     if (fCurrent == kODNULL)
  526.     {
  527.         if ((fNext == kODNULL) && (fPrevious == kODNULL))    // Just starting out
  528.         {
  529.             return this->First();
  530.         }
  531.         else    // Just deleted
  532.         {
  533.             fCurrent = fNext;
  534.             fPrevious = kODNULL;
  535.             fNext = kODNULL;
  536.         }
  537.     }
  538.     else
  539.         fCurrent = fCurrent->GetNext();
  540.     
  541.     if (fCurrent == fSentinel)
  542.         fCurrent = kODNULL;
  543.     return fCurrent;
  544. }
  545.  
  546. //------------------------------------------------------------------------------
  547. // LinkedListIterator::Last
  548. //
  549. // Description
  550. //------------------------------------------------------------------------------
  551.  
  552. Link* LinkedListIterator::Last()
  553. {
  554.     if (fList == kODNULL)
  555.         return kODNULL;
  556.  
  557.     if (fSeed != fList->fSeed)
  558.         THROW(kODErrIteratorOutOfSync);
  559.  
  560.     fCurrent = fList->Last();
  561.     return fCurrent;
  562. }
  563.  
  564. //------------------------------------------------------------------------------
  565. // LinkedListIterator::Previous
  566. //
  567. // Description
  568. //------------------------------------------------------------------------------
  569.  
  570. Link* LinkedListIterator::Previous()
  571. {
  572.     if (fList == kODNULL)
  573.         return kODNULL;
  574.  
  575.     if (fSeed != fList->fSeed)
  576.         THROW(kODErrIteratorOutOfSync);
  577.  
  578.     if (fCurrent == kODNULL)
  579.     {
  580.         if ((fNext == kODNULL) && (fPrevious == kODNULL))    // Just starting out
  581.         {
  582.             return this->Last();
  583.         }
  584.         else    // Just deleted
  585.         {
  586.             fCurrent = fPrevious;
  587.             fPrevious = kODNULL;
  588.             fNext = kODNULL;
  589.         }
  590.     }
  591.     else
  592.         fCurrent = fCurrent->GetPrevious();
  593.  
  594.     if (fCurrent == fSentinel)
  595.         fCurrent = kODNULL;
  596.     return fCurrent;
  597. }
  598.  
  599. //------------------------------------------------------------------------------
  600. // LinkedListIterator::RemoveCurrent
  601. //
  602. // Description
  603. //------------------------------------------------------------------------------
  604.  
  605. void  LinkedListIterator::RemoveCurrent()
  606. {
  607.     if (fList == kODNULL)
  608.         return;
  609.         
  610.     if (fSeed != fList->fSeed)
  611.         THROW(kODErrIteratorOutOfSync);
  612.          
  613.     if (fCurrent != kODNULL)
  614.     {
  615.         fNext = fCurrent->GetNext();
  616.         fPrevious = fCurrent->GetPrevious();
  617.             
  618.         fList->Remove(*fCurrent);
  619.         fCurrent = kODNULL;
  620.         fSeed = fList->fSeed;
  621.     }
  622. }
  623.